package com.sheng.leetcode.year2022.swordfingeroffer.day10;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/09/08
 *
 * 剑指 Offer 46. 把数字翻译成字符串
 *
 * 给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，
 * 1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。
 * 一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
 *
 * 示例 1:
 * 输入: 12258
 * 输出: 5
 * 解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
 *
 * 提示：
 *
 * 0 <= num < 2^31
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Sword0046 {

    @Test
    public void test01() {
        // 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
//        int num = 12258;
        // 3
//        int num = 220;
        // 2
//        int num = 624;
        // 2
//        int num = 41960557;
        // 3
//        int num = 758212932;
        // 4
        int num = 817230807;
        System.out.println(new Solution().translateNum(num));
    }
}
class Solution {
    public int translateNum(int num) {
        //思路分析
        //
        //该题要求按照给定规则将数字翻译成字符串，返回翻译方案的数量，这里求的是方案总数，因此想到动态规划；
        //既然要用动态规划，那么需要定义状态，先将数字num看成 n (num的长度)位数的组合，即，定义状态dp[i]为以第为结尾的方案总数；
        //那么有了状态之后，开始找状态转移方程，如果在"10"~"25"之间的话(包括10和25)，那么当为一个整体时，翻译方案数量为dp[i-2]，当各自分开时，翻译方案为dp[i-1]，于是这种情况下，dp[i] = dp[i-1] + dp[i-2]；
        //如果不能看作一个整体翻译，即不在"10"~"25"之间，那么它们只能分开，翻译方案为dp[i-1]，这时候dp[i] = dp[i-1]；
        //现在要初始化初值了，dp[1] = 1，这个没问题，dp[2]并不能确定，只有当1，2位数组合成的数字在"10"~"25"之间时，dp[2] = 2，因此我们初始化dp[0] = 1。
        //————————————————
        //版权声明：本文为CSDN博主「皮卡qiu~」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
        //原文链接：https://blog.csdn.net/Sruggle/article/details/109782751
        String str = String.valueOf(num);
        int length = str.length();
        int[] ints = new int[length + 1];
        ints[0] = 1;
        ints[1] = 1;
        for (int i = 2; i <= length; i++) {
            String substring = str.substring(i - 2, i);
            if (Integer.parseInt(substring) <= 25 && Integer.parseInt(substring) >= 10) {
                ints[i] = ints[i - 1] + ints[i - 2];
            } else {
                ints[i] = ints[i - 1];
            }
        }
        return ints[length];
//        return transformation(str);
    }

    public int transformation(String str) {
        int length = str.length();
        if (length == 1) {
            return 1;
        } else if (length == 2) {
            if (Integer.valueOf(str) <= 25 && Integer.valueOf(str) >= 10) {
                return 2;
            } else {
                return 1;
            }
        } else {
            int ans = 0;
            String str1 = str.substring(0, length / 2);
            String str2 = str.substring(length / 2);
            int t1 = transformation(str1);
            int t2 = transformation(str2);
            ans = t1 * t2;
            String sss = str1.substring(str1.length() - 1) + str2.substring(0, 1);
            if (Integer.valueOf(sss) <= 25 && Integer.valueOf(sss) >= 10) {
                if (str1.length() > 1 && t1 != 1) {
                    ans += 2;
                } else {
                    ans += 1;
                }
            }
            return ans;
        }
    }
}
